package com.future.offer;

/**
 * Description: 剑指 Offer 53 - I. 在排序数组中查找数字 I
 *
 * @author weiruibai.vendor
 * Date: 2023/2/1 10:38
 */
public class Solution_53 {

    /**
     * 二分查找，找到对应位置，两边扩展
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        int index = process(nums, 0, N - 1, target);
        if (index == -1) {
            return 0;
        }
        return expand(nums, index, target);
    }

    private int expand(int[] nums, int index, int target) {
        int ans = 0;
        // left
        for (int i = index; i >= 0; i--) {
            if (nums[i] == target) {
                ans++;
            }
        }
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[i] == target) {
                ans++;
            }
        }
        return ans;
    }

    private int process(int[] nums, int l, int r, int target) {
        if (l > r) {
            return -1;
        }
        int m = ((l + r) >> 1);
        if (nums[m] == target) {
            return m;
        }
        if (nums[m] > target) {
            return process(nums, l, m - 1, target);
        }
        return process(nums, m + 1, r, target);
    }

}
